{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['广东年润贸易有限公司', '中山市横栏医院'], ['广东年润贸易有限公司', '优达设备国际贸易'], ['广东年润贸易有限公司', '上海复生生物'], ['中山市横栏医院', '上海复生生物'], ['优达设备国际贸易', '徐州市铜山区卫生院'], ['上海复生生物', '徐州市铜山区卫生院'], ['中山市横栏医院', '徐州市铜山区卫生院'], ['徐州市铜山区卫生院', '广东年润贸易有限公司']]\n",
      "['广东年润贸易有限公司', '中山市横栏医院', '优达设备国际贸易', '上海复生生物', '徐州市铜山区卫生院']\n",
      "[[0, 1], [0, 2], [0, 3], [1, 3], [2, 4], [3, 4], [1, 4], [4, 0]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    " \n",
    " \n",
    "if __name__ == '__main__':\n",
    " \n",
    "    # 读入有向图，存储边\n",
    "    f = open('G:\\AI\\PageRank\\input_1.txt',encoding='utf-8')\n",
    "    edges = [line.strip('\\n').split(' ') for line in f]\n",
    "    print(edges)\n",
    " \n",
    "    # 根据边获取节点的集合\n",
    "    nodes = []\n",
    "    for edge in edges:\n",
    "        if edge[0] not in nodes:\n",
    "            nodes.append(edge[0])\n",
    "        if edge[1] not in nodes:\n",
    "            nodes.append(edge[1])\n",
    "    print(nodes)\n",
    " \n",
    "    N = len(nodes)\n",
    " \n",
    "    # 将节点符号（字母），映射成阿拉伯数字，便于后面生成A矩阵/S矩阵\n",
    "    i = 0\n",
    "    node_to_num = {}\n",
    "    for node in nodes:\n",
    "        node_to_num[node] = i\n",
    "        i += 1\n",
    "    for edge in edges:\n",
    "        edge[0] = node_to_num[edge[0]]\n",
    "        edge[1] = node_to_num[edge[1]]\n",
    "    print(edges)\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0. 0. 0. 1.]\n",
      " [1. 0. 0. 0. 0.]\n",
      " [1. 0. 0. 0. 0.]\n",
      " [1. 1. 0. 0. 0.]\n",
      " [0. 1. 1. 1. 0.]]\n"
     ]
    }
   ],
   "source": [
    "    # 生成初步的S矩阵\n",
    "    S = np.zeros([N, N])\n",
    "    for edge in edges:\n",
    "        S[edge[1], edge[0]] = 1\n",
    "    print(S)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.         0.         0.         0.         1.        ]\n",
      " [0.33333333 0.         0.         0.         0.        ]\n",
      " [0.33333333 0.         0.         0.         0.        ]\n",
      " [0.33333333 0.5        0.         0.         0.        ]\n",
      " [0.         0.5        1.         1.         0.        ]]\n"
     ]
    }
   ],
   "source": [
    "    # 计算比例：即进行列的归一化处理\n",
    "    for j in range(N):\n",
    "        sum_of_col = sum(S[:,j])\n",
    "        for i in range(N):\n",
    "            S[i, j] /= sum_of_col\n",
    "    print(S)\n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.03       0.03       0.03       0.03       0.88      ]\n",
      " [0.31333333 0.03       0.03       0.03       0.03      ]\n",
      " [0.31333333 0.03       0.03       0.03       0.03      ]\n",
      " [0.31333333 0.455      0.03       0.03       0.03      ]\n",
      " [0.03       0.455      0.88       0.88       0.03      ]]\n"
     ]
    }
   ],
   "source": [
    "    # 计算矩阵A\n",
    "    alpha = 0.85\n",
    "    A = alpha*S + (1-alpha) / N * np.ones([N, N])\n",
    "    print(A)\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loop...\n",
      "iteration 1: [0.2        0.08666667 0.08666667 0.17166667 0.455     ]\n",
      "iteration 2: [0.41675    0.08666667 0.08666667 0.1235     0.28641667]\n",
      "iteration 3: [0.27345417 0.14807917 0.14807917 0.1849125  0.245475  ]\n",
      "iteration 4: [0.23865375 0.10747868 0.10747868 0.17041233 0.37597656]\n",
      "iteration 5: [0.34958008 0.09761856 0.09761856 0.143297   0.3118858 ]\n",
      "iteration 6: [0.29510293 0.12904769 0.12904769 0.17053558 0.27626612]\n",
      "iteration 7: [0.2648262  0.1136125  0.1136125  0.16845776 0.33949104]\n",
      "iteration 8: [0.31856739 0.10503409 0.10503409 0.1533194  0.31804503]\n",
      "iteration 9: [0.30033828 0.12026076 0.12026076 0.16490025 0.29423996]\n",
      "iteration 10: [0.28010396 0.11509584 0.11509584 0.16620667 0.32349768]\n",
      "iteration 11: [0.30497303 0.10936279 0.10936279 0.15827852 0.31802287]\n",
      "iteration 12: [0.30031944 0.11640902 0.11640902 0.16288821 0.3039743 ]\n",
      "iteration 13: [0.28837816 0.11509051 0.11509051 0.16456434 0.31687648]\n",
      "iteration 14: [0.29934501 0.11170714 0.11170714 0.16062061 0.31662009]\n",
      "iteration 15: [0.29912708 0.11481442 0.11481442 0.16228996 0.30895413]\n",
      "iteration 16: [0.29261101 0.11475267 0.11475267 0.1635488  0.31433485]\n",
      "iteration 17: [0.29718462 0.11290645 0.11290645 0.16167634 0.31532614]\n",
      "iteration 18: [0.29802722 0.11420231 0.11420231 0.16218755 0.31138061]\n",
      "iteration 19: [0.29467352 0.11444104 0.11444104 0.16297703 0.31346736]\n",
      "iteration 20: [0.29644726 0.11349083 0.11349083 0.16212828 0.3144428 ]\n",
      "iteration 21: [0.29727638 0.11399339 0.11399339 0.16222699 0.31250984]\n",
      "iteration 22: [0.29563337 0.11422831 0.11422831 0.1626755  0.31323452]\n",
      "iteration 23: [0.29624934 0.11376279 0.11376279 0.16230982 0.31391527]\n",
      "iteration 24: [0.29682798 0.11393731 0.11393731 0.1622865  0.3130109 ]\n",
      "iteration 25: [0.29605926 0.11410126 0.11410126 0.16252462 0.3132136 ]\n",
      "iteration 26: [0.29623156 0.11388346 0.11388346 0.16237649 0.31362503]\n",
      "iteration 27: [0.29658128 0.11393227 0.11393227 0.16233274 0.31322143]\n",
      "iteration 28: [0.29623821 0.11403136 0.11403136 0.16245258 0.31324648]\n",
      "iteration 29: [0.29625951 0.11393416 0.11393416 0.16239749 0.31347468]\n",
      "iteration 30: [0.29645348 0.11394019 0.11394019 0.16236221 0.31330392]\n",
      "iteration 31: [0.29630833 0.11399515 0.11399515 0.16241973 0.31328163]\n",
      "iteration 32: [0.29628938 0.11395403 0.11395403 0.16240197 0.31340059]\n",
      "iteration 33: [0.2963905  0.11394866 0.11394866 0.16237912 0.31333306]\n",
      "iteration 34: [0.2963331  0.11397731 0.11397731 0.16240549 0.31330679]\n",
      "iteration 35: [0.29631077 0.11396104 0.11396104 0.1624014  0.31336574]\n",
      "iteration 36: [0.29636088 0.11395472 0.11395472 0.16238816 0.31334152]\n",
      "iteration 37: [0.29634029 0.11396891 0.11396891 0.16239967 0.31332221]\n",
      "iteration 38: [0.29632387 0.11396308 0.11396308 0.16239987 0.31335009]\n",
      "iteration 39: [0.29634757 0.11395843 0.11395843 0.16239274 0.31334282]\n",
      "iteration 40: [0.2963414  0.11396515 0.11396515 0.16239748 0.31333083]\n",
      "iteration 41: [0.29633121 0.1139634  0.1139634  0.16239858 0.31334342]\n",
      "iteration 42: [0.29634191 0.11396051 0.11396051 0.16239495 0.31334213]\n",
      "iteration 43: [0.29634081 0.11396354 0.11396354 0.16239676 0.31333536]\n",
      "iteration 44: [0.29633505 0.11396323 0.11396323 0.16239773 0.31334076]\n",
      "iteration 45: [0.29633964 0.1139616  0.1139616  0.16239597 0.31334119]\n",
      "iteration 46: [0.29634001 0.1139629  0.1139629  0.16239658 0.31333761]\n",
      "iteration 47: [0.29633697 0.113963   0.113963   0.16239724 0.31333979]\n",
      "iteration 48: [0.29633882 0.11396214 0.11396214 0.16239642 0.31334048]\n",
      "iteration 49: [0.29633941 0.11396267 0.11396267 0.16239658 0.31333869]\n",
      "iteration 50: [0.29633788 0.11396283 0.11396283 0.16239696 0.31333949]\n",
      "iteration 51: [0.29633856 0.1139624  0.1139624  0.1623966  0.31334003]\n",
      "iteration 52: [0.29633903 0.11396259 0.11396259 0.16239661 0.31333917]\n",
      "iteration 53: [0.2963383  0.11396272 0.11396272 0.16239683 0.31333943]\n",
      "iteration 54: [0.29633851 0.11396252 0.11396252 0.16239668 0.31333978]\n",
      "iteration 55: [0.29633881 0.11396258 0.11396258 0.16239665 0.31333938]\n",
      "iteration 56: [0.29633848 0.11396266 0.11396266 0.16239676 0.31333944]\n",
      "iteration 57: [0.29633852 0.11396257 0.11396257 0.1623967  0.31333964]\n",
      "iteration 58: [0.29633869 0.11396258 0.11396258 0.16239667 0.31333947]\n",
      "iteration 59: [0.29633855 0.11396263 0.11396263 0.16239673 0.31333946]\n",
      "iteration 60: [0.29633854 0.11396259 0.11396259 0.16239671 0.31333957]\n",
      "iteration 61: [0.29633864 0.11396259 0.11396259 0.16239669 0.3133395 ]\n",
      "iteration 62: [0.29633858 0.11396261 0.11396261 0.16239671 0.31333948]\n",
      "iteration 63: [0.29633856 0.1139626  0.1139626  0.16239671 0.31333954]\n",
      "iteration 64: [0.29633861 0.11396259 0.11396259 0.1623967  0.31333951]\n",
      "iteration 65: [0.29633859 0.11396261 0.11396261 0.16239671 0.3133395 ]\n",
      "iteration 66: [0.29633857 0.1139626  0.1139626  0.16239671 0.31333952]\n",
      "iteration 67: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n",
      "iteration 68: [0.29633859 0.1139626  0.1139626  0.1623967  0.3133395 ]\n",
      "iteration 69: [0.29633858 0.1139626  0.1139626  0.16239671 0.31333952]\n",
      "iteration 70: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n",
      "iteration 71: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n",
      "final result: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n"
     ]
    }
   ],
   "source": [
    "    # 生成初始的PageRank值，记录在P_n中，P_n和P_n1均用于迭代\n",
    "    P_n = np.ones(N) / N\n",
    "    P_n1 = np.zeros(N)\n",
    " \n",
    "    e = 100000  # 误差初始化\n",
    "    k = 0   # 记录迭代次数\n",
    "    print('loop...')\n",
    " \n",
    "    while e > 0.00000001:   # 开始迭代\n",
    "        P_n1 = np.dot(A, P_n)   # 迭代公式\n",
    "        e = P_n1-P_n\n",
    "        e = max(map(abs, e))    # 计算误差\n",
    "        P_n = P_n1\n",
    "        k += 1\n",
    "        print('iteration %s:'%str(k), P_n1)\n",
    " \n",
    "    print('final result:', P_n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loop...\n",
      "iteration 1: [0.2        0.08666667 0.08666667 0.17166667 0.455     ]\n",
      "iteration 2: [0.41675    0.08666667 0.08666667 0.1235     0.28641667]\n",
      "iteration 3: [0.27345417 0.14807917 0.14807917 0.1849125  0.245475  ]\n",
      "iteration 4: [0.23865375 0.10747868 0.10747868 0.17041233 0.37597656]\n",
      "iteration 5: [0.34958008 0.09761856 0.09761856 0.143297   0.3118858 ]\n",
      "iteration 6: [0.29510293 0.12904769 0.12904769 0.17053558 0.27626612]\n",
      "iteration 7: [0.2648262  0.1136125  0.1136125  0.16845776 0.33949104]\n",
      "iteration 8: [0.31856739 0.10503409 0.10503409 0.1533194  0.31804503]\n",
      "iteration 9: [0.30033828 0.12026076 0.12026076 0.16490025 0.29423996]\n",
      "iteration 10: [0.28010396 0.11509584 0.11509584 0.16620667 0.32349768]\n",
      "iteration 11: [0.30497303 0.10936279 0.10936279 0.15827852 0.31802287]\n",
      "iteration 12: [0.30031944 0.11640902 0.11640902 0.16288821 0.3039743 ]\n",
      "iteration 13: [0.28837816 0.11509051 0.11509051 0.16456434 0.31687648]\n",
      "iteration 14: [0.29934501 0.11170714 0.11170714 0.16062061 0.31662009]\n",
      "iteration 15: [0.29912708 0.11481442 0.11481442 0.16228996 0.30895413]\n",
      "iteration 16: [0.29261101 0.11475267 0.11475267 0.1635488  0.31433485]\n",
      "iteration 17: [0.29718462 0.11290645 0.11290645 0.16167634 0.31532614]\n",
      "iteration 18: [0.29802722 0.11420231 0.11420231 0.16218755 0.31138061]\n",
      "iteration 19: [0.29467352 0.11444104 0.11444104 0.16297703 0.31346736]\n",
      "iteration 20: [0.29644726 0.11349083 0.11349083 0.16212828 0.3144428 ]\n",
      "iteration 21: [0.29727638 0.11399339 0.11399339 0.16222699 0.31250984]\n",
      "iteration 22: [0.29563337 0.11422831 0.11422831 0.1626755  0.31323452]\n",
      "iteration 23: [0.29624934 0.11376279 0.11376279 0.16230982 0.31391527]\n",
      "iteration 24: [0.29682798 0.11393731 0.11393731 0.1622865  0.3130109 ]\n",
      "iteration 25: [0.29605926 0.11410126 0.11410126 0.16252462 0.3132136 ]\n",
      "iteration 26: [0.29623156 0.11388346 0.11388346 0.16237649 0.31362503]\n",
      "iteration 27: [0.29658128 0.11393227 0.11393227 0.16233274 0.31322143]\n",
      "iteration 28: [0.29623821 0.11403136 0.11403136 0.16245258 0.31324648]\n",
      "iteration 29: [0.29625951 0.11393416 0.11393416 0.16239749 0.31347468]\n",
      "iteration 30: [0.29645348 0.11394019 0.11394019 0.16236221 0.31330392]\n",
      "iteration 31: [0.29630833 0.11399515 0.11399515 0.16241973 0.31328163]\n",
      "iteration 32: [0.29628938 0.11395403 0.11395403 0.16240197 0.31340059]\n",
      "iteration 33: [0.2963905  0.11394866 0.11394866 0.16237912 0.31333306]\n",
      "iteration 34: [0.2963331  0.11397731 0.11397731 0.16240549 0.31330679]\n",
      "iteration 35: [0.29631077 0.11396104 0.11396104 0.1624014  0.31336574]\n",
      "iteration 36: [0.29636088 0.11395472 0.11395472 0.16238816 0.31334152]\n",
      "iteration 37: [0.29634029 0.11396891 0.11396891 0.16239967 0.31332221]\n",
      "iteration 38: [0.29632387 0.11396308 0.11396308 0.16239987 0.31335009]\n",
      "iteration 39: [0.29634757 0.11395843 0.11395843 0.16239274 0.31334282]\n",
      "iteration 40: [0.2963414  0.11396515 0.11396515 0.16239748 0.31333083]\n",
      "iteration 41: [0.29633121 0.1139634  0.1139634  0.16239858 0.31334342]\n",
      "iteration 42: [0.29634191 0.11396051 0.11396051 0.16239495 0.31334213]\n",
      "iteration 43: [0.29634081 0.11396354 0.11396354 0.16239676 0.31333536]\n",
      "iteration 44: [0.29633505 0.11396323 0.11396323 0.16239773 0.31334076]\n",
      "iteration 45: [0.29633964 0.1139616  0.1139616  0.16239597 0.31334119]\n",
      "iteration 46: [0.29634001 0.1139629  0.1139629  0.16239658 0.31333761]\n",
      "iteration 47: [0.29633697 0.113963   0.113963   0.16239724 0.31333979]\n",
      "iteration 48: [0.29633882 0.11396214 0.11396214 0.16239642 0.31334048]\n",
      "iteration 49: [0.29633941 0.11396267 0.11396267 0.16239658 0.31333869]\n",
      "iteration 50: [0.29633788 0.11396283 0.11396283 0.16239696 0.31333949]\n",
      "iteration 51: [0.29633856 0.1139624  0.1139624  0.1623966  0.31334003]\n",
      "iteration 52: [0.29633903 0.11396259 0.11396259 0.16239661 0.31333917]\n",
      "iteration 53: [0.2963383  0.11396272 0.11396272 0.16239683 0.31333943]\n",
      "iteration 54: [0.29633851 0.11396252 0.11396252 0.16239668 0.31333978]\n",
      "iteration 55: [0.29633881 0.11396258 0.11396258 0.16239665 0.31333938]\n",
      "iteration 56: [0.29633848 0.11396266 0.11396266 0.16239676 0.31333944]\n",
      "iteration 57: [0.29633852 0.11396257 0.11396257 0.1623967  0.31333964]\n",
      "iteration 58: [0.29633869 0.11396258 0.11396258 0.16239667 0.31333947]\n",
      "iteration 59: [0.29633855 0.11396263 0.11396263 0.16239673 0.31333946]\n",
      "iteration 60: [0.29633854 0.11396259 0.11396259 0.16239671 0.31333957]\n",
      "iteration 61: [0.29633864 0.11396259 0.11396259 0.16239669 0.3133395 ]\n",
      "iteration 62: [0.29633858 0.11396261 0.11396261 0.16239671 0.31333948]\n",
      "iteration 63: [0.29633856 0.1139626  0.1139626  0.16239671 0.31333954]\n",
      "iteration 64: [0.29633861 0.11396259 0.11396259 0.1623967  0.31333951]\n",
      "iteration 65: [0.29633859 0.11396261 0.11396261 0.16239671 0.3133395 ]\n",
      "iteration 66: [0.29633857 0.1139626  0.1139626  0.16239671 0.31333952]\n",
      "iteration 67: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n",
      "iteration 68: [0.29633859 0.1139626  0.1139626  0.1623967  0.3133395 ]\n",
      "iteration 69: [0.29633858 0.1139626  0.1139626  0.16239671 0.31333952]\n",
      "iteration 70: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n",
      "iteration 71: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n",
      "final result: [0.29633859 0.1139626  0.1139626  0.1623967  0.31333951]\n"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
